package string;

import com.sun.org.apache.xerces.internal.xs.StringList;

import java.util.*;

/**
 * 126.Word Ladder II
 Given two words (beginWord and endWord), and a dictionary's word list,
 find all shortest transformation sequence(s) from beginWord to endWord,

 such that:
 Only one letter can be changed at a time
 Each transformed word must exist in the word list.
 Note that beginWord is not a transformed word.

 Note:
 Return an empty list if there is no such transformation sequence.
 All words have the same length.
 All words contain only lowercase alphabetic characters.
 You may assume no duplicates in the word list.
 You may assume beginWord and endWord are non-empty and are not the same.
 Example 1:

 Input:
 beginWord = "hit",
 endWord = "cog",
 wordList = ["hot","dot","dog","lot","log","cog"]

 Output:
 [
 ["hit","hot","dot","dog","cog"],
 ["hit","hot","lot","log","cog"]
 ]
 Example 2:

 Input:
 beginWord = "hit"
 endWord = "cog"
 wordList = ["hot","dot","dog","lot","log"]

 Output: []

 Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
 */
public class Q126_WordLadderII {

    private Map<String, List<String>> connect = new HashMap<>();

    /**
     * 1.处理字符串，关联
     *  如：hit: hot; hot: hit, dot; ...
     */
    private void handleStr(String beginWord, String endWord, List<String> wordList) {

        for (int i=0; i<wordList.size()-1; i++) {
            for (int j=i+1; j<wordList.size(); j++) {
                String s1 = wordList.get(i);
                String s2 = wordList.get(j);
                if (isMatch(s1, s2)) {
                    if (!connect.containsKey(s1)) {
                        connect.put(s1, new ArrayList<>());
                    }
                    connect.get(s1).add(s2);
                    if (!connect.containsKey(s2)) {
                        connect.put(s2, new ArrayList<>());
                    }
                    connect.get(s2).add(s1);
                }

            }
        }
        //endWord 怎么处理
        connect.put(beginWord, new ArrayList<>());
        for (int i=0; i<wordList.size(); i++) {
            String s1 = wordList.get(i);
            if (isMatch(beginWord, s1)) {
                connect.get(beginWord).add(s1);
            }
        }
        connect.forEach((key, lists)-> lists.forEach(str-> System.out.println(key+" "+str)));
    }

    private boolean isMatch(String s1, String s2) {
        int diffCnt = 0;
        int pos = 0;
        while (pos < s1.length()) {
            if (s1.charAt(pos) != s2.charAt(pos)) {
                diffCnt++;
                if (diffCnt >= 2) {
                    return false;
                }
            }
            pos++;
        }
        return diffCnt == 1;
    }

    private List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        handleStr(beginWord, endWord, wordList);
        List<List<String>> ans = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        cur.add(beginWord);
        int len = wordList.size();
        backtrack(beginWord, endWord, ans, cur, new HashSet<>(), 0, len);
        //ans.forEach(an-> System.out.println(an));
        return ans;
    }
    private void backtrack(String key, String endWord, List<List<String>> ans, List<String> cur, Set<String> flags, int cnt, int len) {
        if (cnt >= len) {
            return ;
        }
        if (endWord.equals(key)) {
            ans.add(new ArrayList<>(cur));
            return ;
        }
        //没有考虑 hit->hot 和 hot->hit,出现死锁导致栈溢出
        for (String str: connect.get(key)) {
            if (flags.contains(str)) {
                continue;
            }
            cur.add(str);
            flags.add(str);
            cnt++;
            backtrack(str, endWord, ans, cur, flags, cnt, len);
            cnt--;
            flags.remove(str);
            cur.remove(cur.size()-1);
        }
    }

    public static void main(String[] args) {
        Q126_WordLadderII q126_wordLadderII = new Q126_WordLadderII();
        List<List<String>> ans = q126_wordLadderII.findLadders("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        ans.forEach(an-> System.out.println(an));
    }
}